#include "Maya2Gunnar.h"
#include <maya/MFnPlugin.h>

/*
	ToDo:
	* If we have a geometry with transparency, make a bsp tree of it, and it that bsp tree is one single branch, then store it as normal geometry.
	* automaticly copied and converted textures
*/

// The philosophy with this export is that it should be very fast to stream the data into the game that uses it.
// We should not care so much about the time being spent on exporting the data.

MStatus initializePlugin( MObject obj )
{ 
	MStatus	status;
	MFnPlugin plugin(obj,"Maya2Gunnar","1.0","Any");
	status=plugin.registerFileTranslator("Maya2Gunnar gun","",Maya2Gunnar::creator);
	return(status);
}

MStatus uninitializePlugin( MObject obj )
{
	MFnPlugin plugin( obj );
	plugin.deregisterFileTranslator("Maya2Gunnar gun");
	return(MS::kSuccess);
}

Maya2Gunnar::Maya2Gunnar(void)
{
}

Maya2Gunnar::~Maya2Gunnar(void)
{
}

bool Maya2Gunnar::haveWriteMethod() const 
{
	return(true);
}

MString Maya2Gunnar::defaultExtension() const
{
	return(MString("gun"));
}

MString Maya2Gunnar::filter() const
{
	return(MString("*.gun"));
}

MPxFileTranslator::MFileKind Maya2Gunnar::identifyFile (
	const MFileObject& file,const char* buffer,short size) const
{
	MString name=file.name();
	unsigned int length=name.length();
	if(length>4)
	{
		MString ext=name.substring(length-4,length);
		if(ext==".gun") {return(kIsMyFileType);}
	}
	return (kNotMyFileType);
}

MStatus Maya2Gunnar::writer(const MFileObject &file,const MString &options,FileAccessMode mode)
{
	// Start with making sure that some important members are cleared.
	m_output=NULL;
	clean();
	// Make sure that we only run if it is an write.
	if(mode!=kExportAccessMode)
	{
		return(MS::kFailure);
	}
	// Get the path and filename to write to and open up a stream for writing.
	const char *path=file.path().asChar();
	const char *name=file.name().asChar();
	MString fullname=file.path()+file.name();
	m_output=new std::ofstream(fullname.asChar(),std::ios::out|std::ios::binary);

	// Write file magic number for easy identification.
	unsigned int magic1,magic2;
	magic1=0xb1d4abad;
	magic2=0x2b17fac;
	push(magic1);
	push(magic2);

	// Below is a do-while(false) loop. It can be seen as a goto with a scope.
	MStatus status=MS::kFailure;
	do
	{
		// Sort out all the graph nodes that we are interested in. This also sorts out all materials.
		m_numofobjects=0;
		MDagPath dagPath;
		MItDag dagIterator(MItDag::kBreadthFirst,MFn::kInvalid,&status);
		if(!status) {break;}
		if(dagIterator.isDone())
		{
			status=MS::kFailure;
			break;
		}
		status=dagIterator.getPath(dagPath);
		if(!status) {break;}
		status=iterateNodes(dagPath);
		if(!status) {break;}

		// Write the materials.
		writeMaterials();
		// Write the geometry and joints.
		status=writeObjects();
		if(!status) {break;}
		// Write the hierarchy and animations.
		status=writeNodes();
	} while(false);

	m_output->close();
	clean();
	return(status);
}

void Maya2Gunnar::clean(void)
{
	if(m_output!=NULL) {delete m_output;}
	m_output=NULL;
	m_nodes.clear();
	m_materials.clear();
	m_iInstances.clear();
	m_jointIndex.clear();
}

bool Maya2Gunnar::isNodeStored(MDagPath path)
{
	std::vector<iInstance>::iterator t;
	for(t=m_iInstances.begin();t<m_iInstances.end();t++)
	{
		if((*t).path.fullPathName()==path.fullPathName()) 
		{
			return(true);
		}
	}
	return(false);
}

MStatus Maya2Gunnar::iterateNodes(MDagPath path)
{
	MStatus status=MS::kSuccess;
	MFnDagNode dagNode(path,&status);
	if(status!=MS::kSuccess) {return(status);}
	MString name=dagNode.name();
	MString tname=dagNode.typeName();

	if(tname=="transform")
	{
		if(name.substring(0,11)=="groundPlane") {return(MS::kSuccess);}
		if(path.hasFn(MFn::kCamera))
		{
			return(MS::kSuccess);
		}
		else if(path.hasFn(MFn::kMesh))
		{
			if(!isNodeStored(path))
			{
				m_iInstances.push_back(iInstance(name,path));
			}
			// Sort out all the attached materials.
			do
			{
				MFnMesh meshNode(path,&status);
				if(!status) {break;}

				MObjectArray sets;
				MObjectArray comps;
				meshNode.getConnectedSetsAndMembers(path.isInstanced()?path.instanceNumber():0,sets,comps,true);

				for(int s=(int)sets.length();--s>=0;)
				{
					MObject comp=comps[s];
					MItMeshPolygon piter(path,comp,&status);
					if(status && !piter.isDone())
					{
						MObject set=sets[s];
						MObject matNode;
						if(getMaterialNode(set,matNode))
						{
							addMaterialToList(matNode,set);
						}
					}
				}
			} while(false);
		}
		m_nodes.push_back(path);
	}
	else if(path.hasFn(MFn::kJoint))
	{
		if(!isNodeStored(path))
		{
			m_iInstances.push_back(iInstance(name,path));
		}
		m_jointIndex.push_back(m_nodes.size());
		m_nodes.push_back(path);
	}

	for(int t=0;t<(int)path.childCount(&status)&&status==MS::kSuccess;t++)
	{
		MObject childObj=path.child(t,&status);
		if(status!=MS::kSuccess) {continue;}
		MDagPath childPath;
		status=path.getAPathTo(childObj,childPath);
		if(status!=MS::kSuccess) {continue;}
		status=iterateNodes(childPath);
	}
	return(status);
}

MStatus Maya2Gunnar::writeObjects(void)
{
	MStatus status;
	MGlobal::viewFrame((double)0);
	// store number of objects
	int numobjects=(int)m_iInstances.size();
	push(numobjects);
	for(int t=0;t<numobjects;t++)
	{
		// store each object
		push_string(m_iInstances[t].name.asChar());
		if(m_iInstances[t].path.hasFn(MFn::kMesh))
		{
			if((status=writeMesh(m_iInstances[t].path))!=MS::kSuccess) {return(status);}
		} 
		else if(m_iInstances[t].path.hasFn(MFn::kJoint))
		{
			if((status=writeJoint(m_iInstances[t].path))!=MS::kSuccess) {return(status);}
		} 
	}
	return(MS::kSuccess);
}

MStatus Maya2Gunnar::getPlug(MFnDagNode &dagNode, const MString &attr, MObject &object)
{
	MStatus status;
	MObject attrobj=dagNode.attribute(attr,&status);
	if(!status) {return(status);}
	MPlug plug(dagNode.object(),attrobj);
	return(plug.getValue(object));
}

void Maya2Gunnar::writeMatrix(const MMatrix &matrix)
{
	for(int j=0;j<4;++j)
	{
		for(int i=0;i<4;++i)
		{
			float v=(float)matrix.matrix[j][i];
			push(v);
		}
	}
}

MStatus Maya2Gunnar::writeJoint(MDagPath &path)
{
	unsigned char objecttype=1;
	push(objecttype);

	MStatus status;
	MFnIkJoint dagNode(path,&status);
	if(!status) {return(status);}

	// write skeleton joint bind transformation.
	MMatrix bindpos(MMatrix::identity);
	do
	{
		MObject matrix;
		status=getPlug(dagNode, MString("bps"), matrix);
		if(!status) {break;}
		MFnMatrixData bindData(matrix,&status);
		if(!status) {break;}
		bindpos=bindData.matrix(&status);
	} while(false);

	// Find the geometry for the skeleton, and store the geometrys matrix as a reference.
	MMatrix geometryRef(MMatrix::identity);
	do
	{
//		MItDependencyGraph dgit(dagNode.object(),MFn::kWeightGeometryFilt,
		MItDependencyGraph dgit(dagNode.object(),MFn::kGeometryFilt,
			MItDependencyGraph::kDownstream,MItDependencyGraph::kDepthFirst,
			MItDependencyGraph::kNodeLevel,&status);
		if(dgit.isDone()) {break;}
		MFnGeometryFilter fnFilter(dgit.thisNode(),&status);
		if(!status) {break;}
		MObjectArray outGem;
		status=fnFilter.getOutputGeometry(outGem);
		if(!status) {break;}
		MFnDagNode gemNode(outGem[0],&status);
		if(!status) {break;}
		MDagPath dagpath;
		status=gemNode.getPath(dagpath);
		if(!status) {break;}
		geometryRef=dagpath.inclusiveMatrix(&status);
	} while(false);

	writeMatrix(geometryRef*bindpos.inverse());
	writeMatrix(geometryRef.inverse());

	return(MS::kSuccess);
}

MStatus Maya2Gunnar::writeMesh(MDagPath &path)
{
	MStatus status;
	MFnMesh dagNode(path,&status);
	if(!status) {return(MS::kFailure);}
	MMatrix matrix=path.inclusiveMatrix(&status);
	MVector ax=MVector(matrix.matrix[0][0],matrix.matrix[1][0],matrix.matrix[2][0]);
	MVector ay=MVector(matrix.matrix[0][1],matrix.matrix[1][1],matrix.matrix[2][1]);
	MVector az=MVector(matrix.matrix[0][2],matrix.matrix[1][2],matrix.matrix[2][2]);
	bool inverted=false;
	if(((ay^az)*ax)<0) 
	{
		inverted=true;
	}
	int flags=0x1;
	MPlug tmpPlug=dagNode.findPlug(MString("ds"),&status);
	if(status==MS::kSuccess)
	{
		bool tmpenum;
		status=tmpPlug.getValue(tmpenum);
		if(status==MS::kSuccess)
		{
			if(tmpenum==true)
			{
				// store no culling of faces
				flags=0x0;
			}
		}
	}

	// Find out if there is any kind of modifier attached to the geometry.
	int t,s;
	MDagPath modifierPath;
	bool gotModifier=false;
	do
	{
		MItDag dagIterator(MItDag::kDepthFirst,MFn::kMesh,&status);
		if(!status) {break;}
		if(!dagIterator.reset(path,MItDag::kDepthFirst,MFn::kMesh)) {break;} 
		for(;!dagIterator.isDone();dagIterator.next())
		{
			if(!dagIterator.getPath(modifierPath)) {continue;}

			MFnDagNode modifierNode(modifierPath,&status);
			if(!status) {continue;}

			if(modifierNode.isIntermediateObject(&status))
			{
				gotModifier=true;
				break;
			}
		}
	} while(false);

	MFloatPointArray vertices;
	MFloatVectorArray normals;
	MFloatArray upoints,vpoints;
	std::vector<std::vector<iWeight>> tmpskin;

	// Pick the vertices, normals, texture coordinates.
	// Must also check if we are using a geometry with a modifier, as we want those values instead if so.
	// We also check that the gfx artist hasn't messed up and continued modelling after applying the skin.
	MObjectArray outGeom;
	int modT,modS;
	if(gotModifier)
	{
		gotModifier=false; // If the skin is fetched ok, then this is set again.
		// Not the prettiest method of doing it, but the most platform independent.
		for(size_t w=0;w<dagNode.numVertices();++w)
		{
			tmpskin.push_back(std::vector<iWeight>());
		}

		// Loop through all joints, and if they are connected to this geometry, store the weights.
		for(modT=0;modT<(int)m_jointIndex.size();++modT)
		{
			MObject tmpnode(m_nodes[m_jointIndex[modT]].node(&status));
			if(!status) {continue;}
			MFnWeightGeometryFilter fnFilt(tmpnode,&status);
			if(status==MS::kSuccess)
			{
				// Rigid skinning or don't know...
				status=fnFilt.getOutputGeometry(outGeom);
				if(!status) {continue;}
				for(modS=0;modS<(int)outGeom.length();++modS)
				{
					if(outGeom[modS]==dagNode.object())
					{
						break;
					}
				}
				if(modS==outGeom.length()) {continue;}
				MFnMesh dagItNode(modifierPath,&status);
				if(dagNode.numVertices()!=dagItNode.numVertices())
				{
					printf("Geometry: %s have been modified after skin was applied. Export aborted!\n",dagNode.name().asChar());
					return(MS::kFailure);
				}

				// Select and fetch all deformers
				MObject defSet=fnFilt.deformerSet(&status);
				if(!status) {break;}
				MFnSet fnSet(defSet,&status);
				if(!status) {break;}
				MSelectionList compList;
				if(!fnSet.getMembers(compList,false)) {break;}

				// Store all the weights for this geometry.
				// This just gotta be bugged, verify working!
				for(int cl=0;cl<(int)compList.length();++cl)
				{
					MObject comp;
					MDagPath dp;
					if(!compList.getDagPath(modS,dp,comp)) {continue;}
					MItGeometry itGeo( dp,comp,&status);
					if(!status) {continue;}

					for(;!itGeo.isDone();itGeo.next())
					{
						gotModifier=true;	// OK, now we really have a skin!
						MWeight wt=itGeo.weight(&status);
						if(!status) {continue;}
						float inf=wt.influence();
						if(inf>0.001f)	// Do not handle weights that have very little influence
						{
							tmpskin[itGeo.index()].push_back(iWeight(modT,inf));
						}
					}
				}
			}
		}
		// No weightfilter was applied to the geometry... Try skincluster.
		if(!gotModifier)
		{
			do
			{
				MFnMesh dagItNode(modifierPath,&status);
				if(!status) {continue;}
				MItDependencyGraph dgit(dagItNode.object(),MFn::kSkinClusterFilter,
					MItDependencyGraph::kDownstream,MItDependencyGraph::kDepthFirst,
					MItDependencyGraph::kNodeLevel,&status);
				if(dgit.isDone()) {continue;}
				MFnSkinCluster fnCluster(dgit.thisNode(),&status);
				if(status==MS::kSuccess)
				{
					// Smooth skinning
					status=fnCluster.getOutputGeometry(outGeom);
					if(!status) {continue;}
					for(modS=0;modS<(int)outGeom.length();++modS)
					{
						if(outGeom[modS]==dagNode.object())
						{
							break;
						}
					}
					if(modS==outGeom.length()) {continue;}
					if(dagNode.numVertices()!=dagItNode.numVertices())
					{
						printf("Geometry: %s have been modified after skin was applied. Export aborted!\n",dagNode.name().asChar());
						return(MS::kFailure);
					}
					MDagPathArray infs;
					unsigned int nInfs = fnCluster.influenceObjects(infs);
					MIntArray infIndex;
					for(t=0;t<(int)infs.length();t++)
					{
						for(modT=0;modT<(int)m_jointIndex.size();++modT)
						{
							if(m_nodes[m_jointIndex[modT]]==infs[t])
							{
								infIndex.append(modT);
							}
						}
					}

					MItGeometry itGeo(path,&status);
					if(!status) {continue;}
					for(;!itGeo.isDone();itGeo.next())
					{
						gotModifier=true;	// OK, now we really have a skin!
						MObject comp = itGeo.component();
						MFloatArray wts;
						int infCount;
						fnCluster.getWeights(path,comp,wts,(unsigned int&)infCount);
						while(--infCount>=0)
						{
							float inf=wts[infCount];
							if(inf>0.001f)	// Do not handle weights that have very little influence
							{
								tmpskin[itGeo.index()].push_back(iWeight(infIndex[infCount],inf));
							}
						}
					}
				}
			} while(false);
		}
	}
	if(!gotModifier)
	{
		tmpskin.clear();
	}
/*
	if(gotModifier)
	{
		dagItNode.getPoints(vertices);
		dagItNode.getNormals(normals);
		dagItNode.getUVs(upoints,vpoints);
	}
	else
	{
*/
		dagNode.getPoints(vertices);
		dagNode.getNormals(normals);
		dagNode.getUVs(upoints,vpoints);
//	}

	unsigned char objecttype=0;
	push(objecttype);
	push(flags);

	unsigned int inst=0;
	if(path.isInstanced())
	{
		inst=path.instanceNumber();
	}

	MObjectArray shaders;
	MIntArray shaderindices;
	MIntArray mindices;
	dagNode.getConnectedShaders(inst,shaders,shaderindices);

	// reserve working memory
	MIntArray faces,tfaces,nfaces,materials;
	int numtriangles=0;

	// build data by iterating through all faces.
	// This is really slow, and most likely done in a stupid way...
	// Someone smarter than me is most welcome to optimize this.
	int matid,shaderIndex;
	MItMeshPolygon polyIter(path);
	int tmp;
	for(t=0;!polyIter.isDone();polyIter.next())
	{
		matid=0;
		shaderIndex=shaderindices[t];
		if(shaderIndex>=0)
		{
			matid=getMaterialID(shaders[shaderIndex]);
		}
		if(polyIter.hasValidTriangulation())
		{
			MPointArray points;
			MIntArray indlist;	// object space indices
			polyIter.getTriangles(points,indlist,MSpace::kObject);
			// We know that we have at least one triangle here, so calculate the face normal.
			MFloatVector norm,v1,v2;
			v1=vertices[indlist[0]]-vertices[indlist[1]];
			v2=vertices[indlist[2]]-vertices[indlist[1]];
			norm=v1^v2;
			for(s=0;s<(int)indlist.length();s++)
			{
				faces.append(indlist[s]);
				// find the object space indices for texture and normal.
				for(tmp=0;tmp<(int)polyIter.polygonVertexCount();tmp++)
				{
					if(polyIter.vertexIndex(tmp)==indlist[s])
					{
						nfaces.append(polyIter.normalIndex(tmp));
						polyIter.getUVIndex(tmp,tmp,NULL);
						tfaces.append(tmp);
						break;
					}
				}
				if((s%3)==0)
				{
					mindices.append(matid);
					numtriangles++;
				}
			}
		}
		t++;
	}

	// Copy all vertex indexes to skin indexes.
	MIntArray sfaces;
	if(gotModifier)
	{
		sfaces.copy(faces);
	}

	// Clear texture indexes if they are unused.
	if(upoints.length()==0)
	{
		upoints.append(0);
		vpoints.append(0);
		for(t=0;t<(int)tfaces.length();t++) {tfaces[t]=0;}
	}

	// Go through all indexes and make sure that we do not have any duplicates, this will optimise the reindexing we will do later.

	{
		// Remove duplicates for vertices
		MIntArray tmpfaces;
		tmpfaces.copy(faces);
		faces.clear();
		MFloatPointArray tmpvertices;
		tmpvertices.copy(vertices);
		vertices.clear();
		for(t=0;t<(int)tmpfaces.length();++t)
		{
			for(s=0;s<(int)vertices.length();++s)
			{
				if(tmpvertices[tmpfaces[t]]==vertices[s])
				{
					// Duplicate, reindex
					faces.append(s);
					break;
				}
			}
			if(s==(int)vertices.length())
			{
				faces.append(vertices.length());
				vertices.append(tmpvertices[tmpfaces[t]]);
			}
		}
	}

	{
		// Remove duplicates for normals
		MIntArray tmpfaces;
		tmpfaces.copy(nfaces);
		nfaces.clear();
		MFloatVectorArray tmpvertices;
		tmpvertices.copy(normals);
		normals.clear();
		for(t=0;t<(int)tmpfaces.length();++t)
		{
			for(s=0;s<(int)normals.length();++s)
			{
				if(tmpvertices[tmpfaces[t]]==normals[s])
				{
					// Duplicate, reindex
					nfaces.append(s);
					break;
				}
			}
			if(s==(int)normals.length())
			{
				nfaces.append(normals.length());
				normals.append(tmpvertices[tmpfaces[t]]);
			}
		}
	}

	{
		// Remove duplicates for uv coordinates
		MIntArray tmpfaces;
		tmpfaces.copy(tfaces);
		tfaces.clear();
		MFloatArray tmpupoints,tmpvpoints;
		tmpupoints.copy(upoints);
		tmpvpoints.copy(vpoints);
		upoints.clear();
		vpoints.clear();
		for(t=0;t<(int)tmpfaces.length();++t)
		{
			for(s=0;s<(int)upoints.length();++s)
			{
				if(tmpupoints[tmpfaces[t]]==upoints[s]&&tmpvpoints[tmpfaces[t]]==vpoints[s])
				{
					// Duplicate, reindex
					tfaces.append(s);
					break;
				}
			}
			if(s==(int)upoints.length())
			{
				tfaces.append(upoints.length());
				upoints.append(tmpupoints[tmpfaces[t]]);
				vpoints.append(tmpvpoints[tmpfaces[t]]);
			}
		}
	}

	std::vector<std::vector<iWeight>> skin;
	if(gotModifier)
	{
		// Normalize skinning weights before we search for duplicates.
		for(s=0;s<(int)tmpskin.size();++s)
		{
			std::vector<iWeight> &ref=tmpskin[s];
			float len=0;
			for(t=0;t<ref.size();++t)
			{
				len+=ref[t].weight*ref[t].weight;
			}
			if(len!=0)
			{
				len=sqrt(len);
				for(t=0;t<ref.size();++t)
				{
					ref[t].weight=ref[t].weight/len;
				}
			}
			else
			{
				for(t=0;t<ref.size();++t)
				{
					ref[t].weight=1.0f;
				}
			}
		}

		// Remove duplicates for skinweights
		MIntArray tmpfaces;
		tmpfaces.copy(sfaces);
		sfaces.clear();
		for(t=0;t<(int)tmpfaces.length();++t)
		{
			std::vector<iWeight> &ref1=tmpskin[tmpfaces[t]];
			for(s=0;s<(int)skin.size();++s)
			{
				std::vector<iWeight> &ref2=skin[s];
				if(ref1.size()!=ref2.size()) {continue;}
				for(tmp=0;tmp<(int)ref1.size();++tmp)
				{
					if(ref1[tmp]!=ref2[tmp]) {break;}
				}
				if(tmp==(int)ref1.size())
				{
					// Duplicate, reindex
					sfaces.append(s);
					break;
				}
			}
			if(s==(int)skin.size())
			{
				sfaces.append((int)skin.size());
				skin.push_back(tmpskin[tmpfaces[t]]);
			}
		}
		tmpskin.clear();
	}
	
	float box[6]={1000000,1000000,1000000,-1000000,-1000000,-1000000};
	for(t=0;t<(int)vertices.length();t++)
	{
		if(vertices[t].x<box[0]) {box[0]=vertices[t].x;}
		else if(vertices[t].x>box[3]) {box[3]=vertices[t].x;}
		if(vertices[t].y<box[1]) {box[1]=vertices[t].y;}
		else if(vertices[t].y>box[4]) {box[4]=vertices[t].y;}
		if(vertices[t].z<box[2]) {box[2]=vertices[t].z;}
		else if(vertices[t].z>box[5]) {box[5]=vertices[t].z;}
	}
	for(t=0;t<6;t++)
	{
		push(box[t]);
	}

	// sort materials into submeshes and store
	MIntArray submats;
	for(t=0;t<(int)mindices.length();t++)
	{
		for(s=0;s<(int)submats.length();s++)
		{
			if(mindices[t]==submats[s])
			{
				break;
			}
		}
		if(s==(int)submats.length())
		{
			submats.append(mindices[t]);
		}
	}

	tmp=(int)submats.length();
	push(tmp);	// numofsubmeshes

	// sort triangles so they come in material order.
	t=0;
	while(t<((int)mindices.length()-1))
	{
		s=t+1;
		if(mindices[t]!=mindices[s])
		{
			while(s<(int)mindices.length())
			{
				if(mindices[t]==mindices[s])
				{
					t++;
					tmp=mindices[t];
					mindices[t]=mindices[s];
					mindices[s]=tmp;

					tmp=faces[t*3+0];
					faces[t*3+0]=faces[s*3+0];
					faces[s*3+0]=tmp;
					tmp=faces[t*3+1];
					faces[t*3+1]=faces[s*3+1];
					faces[s*3+1]=tmp;
					tmp=faces[t*3+2];
					faces[t*3+2]=faces[s*3+2];
					faces[s*3+2]=tmp;

					tmp=nfaces[t*3+0];
					nfaces[t*3+0]=nfaces[s*3+0];
					nfaces[s*3+0]=tmp;
					tmp=nfaces[t*3+1];
					nfaces[t*3+1]=nfaces[s*3+1];
					nfaces[s*3+1]=tmp;
					tmp=nfaces[t*3+2];
					nfaces[t*3+2]=nfaces[s*3+2];
					nfaces[s*3+2]=tmp;

					tmp=tfaces[t*3+0];
					tfaces[t*3+0]=tfaces[s*3+0];
					tfaces[s*3+0]=tmp;
					tmp=tfaces[t*3+1];
					tfaces[t*3+1]=tfaces[s*3+1];
					tfaces[s*3+1]=tmp;
					tmp=tfaces[t*3+2];
					tfaces[t*3+2]=tfaces[s*3+2];
					tfaces[s*3+2]=tmp;
				}
				s++;
			}
		}
		t++;
	}
	
	// reindex triangles so the same indexing can be used for vertices, normals and textures.

	// Create a huge set where wich we can use to determine if a vertex is unique or not.
	std::vector<iVertexSet> hugeset;
	for(t=0;t<(int)faces.length();t++)
	{
		if(gotModifier)
		{
			if(m_materials[mindices[(int)(t/3)]].gottexture)
			{
				hugeset.push_back(iVertexSet(faces[t],nfaces[t],tfaces[t],sfaces[t]));
			}
			else
			{
				hugeset.push_back(iVertexSet(faces[t],nfaces[t],0,sfaces[t]));
			}
		}
		else
		{
			if(m_materials[mindices[(int)(t/3)]].gottexture)
			{
				hugeset.push_back(iVertexSet(faces[t],nfaces[t],tfaces[t],0));
			}
			else
			{
				hugeset.push_back(iVertexSet(faces[t],nfaces[t],0,0));
			}
		}
	}

	// create the new indexes per submesh
	s=(int)mindices.length();
	for(t=0;t<(int)mindices.length();t=s)
	{
		for(s=t;s<(int)mindices.length();s++)
		{
			if(mindices[t]!=mindices[s]) {break;}
		}
		// from t to <s is the same material
		MFloatPointArray t_vertices;
		MFloatVectorArray t_normals;
		MFloatArray t_upoints,t_vpoints;
		std::vector<std::vector<iWeight>> t_skin;
		int skinwidth=0;

		int ft=t*3;
		int fs=s*3;
		int indx=0;
		MFloatPoint center;
		for(int t1=ft;t1<fs;t1++)
		{
			faces[t1]=-1;
			for(int s1=ft;s1<t1;s1++)
			{
				if(hugeset[t1]==hugeset[s1])
				{
					faces[t1]=faces[s1];
					break;
				}
			}
			if(faces[t1]==-1)
			{
				// new index
				faces[t1]=indx++;
				center+=MFloatVector(vertices[hugeset[t1].idx]);
				t_vertices.append(vertices[hugeset[t1].idx]);
				t_normals.append(normals[hugeset[t1].nidx]);
				t_upoints.append(upoints[hugeset[t1].tidx]);
				t_vpoints.append(vpoints[hugeset[t1].tidx]);
				if(gotModifier)
				{
					t_skin.push_back(skin[hugeset[t1].widx]);
					int skinw=(int)skin[hugeset[t1].widx].size();
					if(skinwidth<skinw) {skinwidth=skinw;}
				}
			}
		}
		center=center/(float)(t_vertices.length());
		unsigned short to=(unsigned short)mindices[t];

		if(m_materials[mindices[t]].sortalpha&&skinwidth==0&&ALLOW_USE_OF_BSP==1)
		{
			BSPTree *bsp=new BSPTree(t_vertices,t_normals,t_upoints,t_vpoints,faces,ft,fs-ft,m_materials[to].gottexture);
			bsp->generate();
			int trinum;
			bsp->extractVertices(t_vertices,t_normals,t_upoints,t_vpoints,trinum);
			// store bsp
			push(to);
			push(center.x);
			push(center.y);
			push(center.z);
			push(trinum);
			int vertnum=t_vertices.length();
			push(vertnum);
			push(skinwidth);
			unsigned char meshtype=1;
			push(meshtype);
			bsp->pushTriangles(this);
			delete bsp;
		}
		else
		{
			// store faces
			push(to);
			push(center.x);
			push(center.y);
			push(center.z);
			int trinum=s-t;
			push(trinum);
			int vertnum=t_vertices.length();
			push(vertnum);
			push(skinwidth);
			unsigned char meshtype=0;
			push(meshtype);
			unsigned short ust;
			for(tmp=ft;tmp<fs;tmp+=3)
			{
				ust=(unsigned short)faces[tmp];
				push(ust);
				if(inverted)
				{
					ust=(unsigned short)faces[tmp+2];
					push(ust);
					ust=(unsigned short)faces[tmp+1];
					push(ust);
				}
				else
				{
					ust=(unsigned short)faces[tmp+1];
					push(ust);
					ust=(unsigned short)faces[tmp+2];
					push(ust);
				}
			}
		}

		for(tmp=0;tmp<(int)t_vertices.length();tmp++)
		{
			if(m_materials[to].gottexture)
			{
				push(t_upoints[tmp]);
				push(t_vpoints[tmp]);
			}
			push(t_normals[tmp].x);
			push(t_normals[tmp].y);
			push(t_normals[tmp].z);
			push(t_vertices[tmp].x);
			push(t_vertices[tmp].y);
			push(t_vertices[tmp].z);
		}

		// Store skin weights
		for(tmp=0;tmp<(int)t_skin.size();tmp++)
		{
			std::vector<iWeight> &ref=t_skin[tmp];
			int sk=0;
			for(;sk<(int)ref.size();++sk)
			{
				push(ref[sk].weight);
			}
			// Add with zero influese weights so we keep a fixed skinwidth for all vertices.
			for(;sk<skinwidth;++sk)
			{
				float w=0;
				push(w);
			}
		}
		// Store skin joint indexes
		for(tmp=0;tmp<(int)t_skin.size();tmp++)
		{
			std::vector<iWeight> &ref=t_skin[tmp];
			int sk=0;
			for(;sk<(int)ref.size();++sk)
			{
				push(ref[sk].index);
			}
			for(;sk<skinwidth;++sk)
			{
				unsigned char idx=0;
				push(idx);
			}
		}

	}

	return(MS::kSuccess);
}

int Maya2Gunnar::getParentIndex(size_t node)
{
	MDagPath path=m_nodes[node];
	while(path.pop(1)==MS::kSuccess)
	{
		for(int t=(int)m_nodes.size();--t>=0;)
		{
			if(m_nodes[t]==path) {return(t);}
		}
	}
	return(-1);
}

int Maya2Gunnar::getHierarchy(MObject node)
{
	for(int t=(int)m_nodes.size();--t>=0;)
	{
		if(node==m_nodes[t].node())
		{
			return(t);
		}
	}
	return(-1);	// error
}

bool Maya2Gunnar::supportedMaterialType(MString tname)
{
	return(tname=="phong"||tname=="phongE"||tname=="blinn"||tname=="lambert"||tname=="layeredShader"||tname=="anisotropic");
}

int Maya2Gunnar::getMaterialID(MObject shader)
{
	MStatus status;
	MItDependencyGraph dgit(shader,MFn::kInvalid,
		MItDependencyGraph::kUpstream,MItDependencyGraph::kBreadthFirst,
		MItDependencyGraph::kNodeLevel,&status);
	for(;!dgit.isDone();dgit.next())
	{
		MFnDependencyNode tmpnode(dgit.thisNode(),&status);
		if(supportedMaterialType(tmpnode.typeName(&status)))
		{
			for(int t=(int)m_materials.size();--t>=0;)
			{
				if(tmpnode.name()==m_materials[t].name)
				{
					return(t);
				}
			}
		}
	}
	return(0);
}

bool Maya2Gunnar::getMaterialNode(MObject shader, MObject &ret)
{
	MStatus status;
	MItDependencyGraph dgit(shader,MFn::kInvalid,
		MItDependencyGraph::kUpstream,MItDependencyGraph::kBreadthFirst,
		MItDependencyGraph::kNodeLevel,&status);
	for(;!dgit.isDone();dgit.next())
	{
		MFnDependencyNode tmpnode(dgit.thisNode(),&status);
		if(supportedMaterialType(tmpnode.typeName(&status)))
		{
			for(int t=(int)m_materials.size();--t>=0;)
			{
				if(tmpnode.name()==m_materials[t].name)
				{
					return(false);
				}
			}
			ret=dgit.thisNode();
			return(true);
		}
	}
	return(false);
}


void Maya2Gunnar::writeMaterials(void)
{
	// write all materials
	int nummaterial=(int)m_materials.size();
	push(nummaterial);
	for(int t=0;t<nummaterial;t++)
	{
		m_cmaterial=t;
		iMaterial &mtl=m_materials[t];
		push_string(mtl.name.asChar());
		push(mtl.diffuse[0]);push(mtl.diffuse[1]);push(mtl.diffuse[2]);
		push(mtl.specular[0]);push(mtl.specular[1]);push(mtl.specular[2]);
		push(mtl.ambient[0]);push(mtl.ambient[1]);push(mtl.ambient[2]);
		push(mtl.illumination[0]);push(mtl.illumination[1]);push(mtl.illumination[2]);
		push(mtl.shininess);
		push(mtl.transparency);
		mtl.gottexture=findAndWriteTextures(m_materials[t].node);
	}
}

void Maya2Gunnar::addMaterialToList(MObject srcNode,MObject rootNode)
{
	MStatus status;
 	MColor mcolor;
	float color[3];
	float factor;
	MFnBlinnShader fnBlinn;
	iMaterial m;

	MFnDependencyNode tmpNode(srcNode,&status);
	MString tname=tmpNode.typeName(&status);

	MFnLambertShader fnShader(srcNode,&status);
	MFnDependencyNode depNode(rootNode,&status);
	m.name=fnShader.name();
	m.node=srcNode;
	m.sortalpha=false;
	m.specular[0]=m.specular[1]=m.specular[2]=0;
	m.shininess=1;

	if(tname=="layeredShader")
	{
		m.diffuse[0]=m.diffuse[1]=m.diffuse[2]=0.5;
		m.ambient[0]=m.ambient[1]=m.ambient[2]=0;
		m.illumination[0]=m.illumination[1]=m.illumination[2]=0;
		m.transparency=0;
	}
	// Get material color
 	mcolor=fnShader.color(&status);
 	mcolor.get(m.diffuse);
	// store diffuse component
 	factor=fnShader.diffuseCoeff(&status);
	m.diffuse[0]*=factor;
	m.diffuse[1]*=factor;
	m.diffuse[2]*=factor;

	// Get ambient color
 	mcolor=fnShader.ambientColor(&status);
 	mcolor.get(m.ambient);

	// Get selfillumination
 	mcolor=fnShader.incandescence(&status);
 	mcolor.get(m.illumination);

	// Get transparecy
 	mcolor=fnShader.transparency(&status);
 	mcolor.get(color);
	m.transparency=(color[0]+color[1]+color[2])/3;

	if(tname!="lambert")
	{
		MFnReflectShader fnReflect;
	 	status=fnReflect.setObject(srcNode);

		// Get specular color
		//factor=fnReflect.reflectivity(&status);
		factor=1.0f;
		mcolor=fnReflect.specularColor(&status);
		mcolor.get(m.specular);

		if(tname=="blinn")
		{
			fnBlinn.setObject(srcNode);
//			rolloff=fnBlinn.specularRollOff(&status);
//			factor*=rolloff;
			m.shininess=fnBlinn.eccentricity(&status);
			if(m.shininess==0) {m.shininess=100;}
			else	
			{
				m.shininess=1/(m.shininess*m.shininess);
			}
		}
		m.specular[0]*=factor;
		m.specular[1]*=factor;
		m.specular[2]*=factor;

	    // Fill in the shininess depending on type
		if(tname=="phongE"||tname=="anisotropic")
		{
			// use the "roughness" attribute for shininess
			MFnDependencyNode curSNode(srcNode,&status);
			MPlug vPlug=curSNode.findPlug("roughness",&status);
			double roughness;
			if(status==MS::kSuccess)
			{
				vPlug.getValue(roughness);
				m.shininess=(float)roughness;
			}   
		}
		else if(tname=="phong")
		{
			MFnPhongShader fnPhong;
			status=fnPhong.setObject(srcNode);
			factor=fnPhong.cosPower(&status);
			m.shininess=factor*4;
		}
	}

	MObject tmpObj;
	if((findTextureAttribute(fnShader,"c",tmpObj))!=NULL)
	{
		// Adjust diffuse color after diffuse texture.
		float tmpfloat,tmpstrength;
		MPlug tmpPlug;
		MFnDependencyNode texNode(tmpObj,&status);
		if(status==MS::kSuccess)
		{
			tmpstrength=0;
			tmpfloat=1;
			tmpPlug=texNode.findPlug(MString("cgr"),&status);
			if(status==MS::kSuccess)
			{
				status=tmpPlug.getValue(tmpfloat);
				if(status!=MS::kSuccess) {tmpfloat=1;}
			}
			tmpstrength+=tmpfloat;
			tmpfloat=1;
			tmpPlug=texNode.findPlug(MString("cgg"),&status);
			if(status==MS::kSuccess)
			{
				status=tmpPlug.getValue(tmpfloat);
				if(status!=MS::kSuccess) {tmpfloat=1;}
			}
			tmpstrength+=tmpfloat;
			tmpfloat=1;
			tmpPlug=texNode.findPlug(MString("cgb"),&status);
			if(status==MS::kSuccess)
			{
				status=tmpPlug.getValue(tmpfloat);
				if(status!=MS::kSuccess) {tmpfloat=1;}
			}
			tmpstrength+=tmpfloat;
			tmpstrength/=3;
			m.diffuse[0]=(m.diffuse[0]*(1-tmpstrength))+tmpstrength;
			m.diffuse[1]=(m.diffuse[1]*(1-tmpstrength))+tmpstrength;
			m.diffuse[2]=(m.diffuse[2]*(1-tmpstrength))+tmpstrength;
		}
	}

	if( (findTextureAttribute(fnShader,"it",tmpObj))!=NULL ||(m.transparency!=0&&((findTextureAttribute(fnShader,"c",tmpObj))!=NULL||(findTextureAttribute(fnShader,"rc",tmpObj))!=NULL)))
	{
		// we got a alpha channel in the texture. Need to sort it extra carefully...
		m.sortalpha=true;
	}
	m_materials.push_back(m);
}

bool Maya2Gunnar::findTextureAttribute(MFnDependencyNode &depNode,char *name,MObject &found)
{
	MStatus status;
	MPlug tmpPlug=depNode.findPlug(MString(name),&status);
	if(status==MS::kSuccess)
	{
		MPlugArray connections;
		if(tmpPlug.connectedTo(connections,true,false,&status))
		{
			if(status==MS::kSuccess)
			{
				for(int t=0;t<(int)connections.length();t++)
				{
					MObject attr=connections[t].node(&status);
					if(status!=MS::kSuccess) {continue;}
					MFn::Type type=attr.apiType();
					if(type==MFn::kProjection)
					{
						MFnDependencyNode depNode2(attr,&status);
						if(status!=MS::kSuccess) {return(false);}
						return(findTextureAttribute(depNode2,"im",found));
					}
					else if(type==MFn::kFileTexture)
					{
						found=attr;
						return(true);
					}
				}
			}
		}
	}
	return(false);
}

bool Maya2Gunnar::findAndWriteTextures(MObject node)
{
	MObjectArray textures;
	MObject	tmpObj;
//	MObject	tmpObj_sc;
	MStatus status;
	MFnDependencyNode depNode(node,&status);
	if(status!=MS::kSuccess) {return(false);}

// bitmap types:
// 0 = diffuse
// 1 = reflection
	int existing=0;
	bool gottexture=false;
	if((findTextureAttribute(depNode,"c",tmpObj))!=NULL)
	{
		existing|=1;
		textures.append(tmpObj);
		gottexture=true;
	}
	if((findTextureAttribute(depNode,"rc",tmpObj))!=NULL)
	{
		existing|=2;
		textures.append(tmpObj);
		gottexture=true;
	}
	push(existing);
	int i=0;
	int j=0;
	while(existing!=0)
	{
		if((existing&1))
		{
			writeTexture(depNode,textures[j],i);
			j++;
		}
		i++;
		existing>>=1;
	}
	return(gottexture);
}

void Maya2Gunnar::writeTexture(MFnDependencyNode &depNode,MObject tmpObj,int type)
{
	iBitmapSetting parm;
	bool tmpbool;
	float tmpfloat;
	int tmpint;
	MStatus status;
	MPlug tmpPlug;
	MString texturename;
	MFnDependencyNode texNode(tmpObj,&status);
	if(status!=MS::kSuccess) {return;}

	tmpPlug=texNode.findPlug(MString("ftn"),&status);
	if(status!=MS::kSuccess) {return;}
	status=tmpPlug.getValue(texturename);
	if(status!=MS::kSuccess) {return;}

	tmpint=texturename.rindex('\\');
	if(tmpint<texturename.rindex('/'))
	{
		tmpint=texturename.rindex('/');
	}
	if(tmpint<0) {tmpint=0;}
	push_string(texturename.substring(tmpint+1,texturename.length()).asChar());

	parm.angle=0;
	parm.strength=0;
	parm.uoffset=parm.voffset=0;
	parm.utile=parm.vtile=1;
	parm.filter=0;

	MObject mapobject;
	if(findMappingAttribute(texNode,mapobject))
	{
		MFnDependencyNode mapNode(mapobject,&status);
		if(status==MS::kSuccess)
		{
			if(getPlugVal(mapNode,"wu",tmpbool)==MS::kSuccess)
			{
				parm.filter|=tmpbool?0:2;
			}
			if(getPlugVal(mapNode,"wv",tmpbool)==MS::kSuccess)
			{
				parm.filter|=tmpbool?0:4;
			}
			getPlugVal(mapNode,"ofu",parm.uoffset);
			getPlugVal(mapNode,"ofv",parm.voffset);
			getPlugVal(mapNode,"reu",parm.utile);
			getPlugVal(mapNode,"rev",parm.vtile);
			getPlugVal(mapNode,"rotateFrame",parm.angle);
			getPlugVal(mapNode,"rotateUV",parm.angle);
			parm.angle=-parm.angle;
		}
	}

	if(getPlugVal(texNode,"ail",tmpbool)==MS::kSuccess)
	{
		parm.filter|=tmpbool?0:8;
	}

	parm.strength=1;
	if(type==0)
	{
		getPlugVal(texNode,"cgr",parm.strength);
		tmpfloat=1;
		getPlugVal(texNode,"cgg",tmpfloat);
		parm.strength+=tmpfloat;
		tmpfloat=1;
		getPlugVal(texNode,"cgb",tmpfloat);
		parm.strength=(parm.strength+tmpfloat)/3;
	}
	else
	{
		getPlugVal(depNode,"rfl",parm.strength);
	}
	if(getPlugVal(texNode,"ft",tmpint)==MS::kSuccess)
	{
		if(tmpint==0)
		{
			parm.filter|=1;
		}
	}
	push(parm.strength);
	push(parm.filter);
	if(type==0)
	{
		// save params for later
		iBitmapSetting &bp=m_materials[m_cmaterial].textureparams;
		bp.angle=parm.angle;
		bp.filter=parm.filter;
		bp.strength=parm.strength;
		bp.uoffset=parm.uoffset;
		bp.voffset=parm.voffset;
		bp.utile=parm.utile;
		bp.vtile=parm.vtile;
	}
}

bool Maya2Gunnar::findMappingAttribute(MFnDependencyNode &depNode,MObject &found)
{
	MStatus status;
	MPlug tmpPlug=depNode.findPlug(MString("uvCoord"),&status);
	if(status==MS::kSuccess)
	{
		MPlugArray connections;
		if(tmpPlug.connectedTo(connections,true,false,&status))
		{
			if(status==MS::kSuccess)
			{
				for(int t=0;t<(int)connections.length();t++)
				{
					MObject attr=connections[t].node(&status);
					if(status!=MS::kSuccess) {continue;}
					if(attr.apiType()==MFn::kPlace2dTexture)
					{
						found=attr;
						return(true);
					}
				}
			}
		}
	}
	return(false);
}

MStatus Maya2Gunnar::writeNodes(void)
{
	MStatus status;
	int tmpval;
	int start,range;
	size_t t;
	MMatrix matrix,pmatrix;
	int parent,node;

	start=(int)MAnimControl::minTime().as(MTime::kGames);
	range=(int)MAnimControl::maxTime().as(MTime::kGames)-start;
	if(range==0) {range=1;}

	m_matrixes=new MMatrix*[range*m_nodes.size()];

	for(int num=0;num<range;num++)
	{
		MAnimControl::setCurrentTime(MTime((double)(num+start),MTime::kGames));
		for(node=0;node<(int)m_nodes.size();node++)
		{
			parent=getParentIndex(node);
			matrix.setToIdentity();
			matrix=m_nodes[node].inclusiveMatrix(&status);
			if(status==MS::kSuccess)
			{
				if(parent!=-1)
				{
					pmatrix=m_nodes[parent].inclusiveMatrix(&status);
					if(status==MS::kSuccess)
					{
						matrix*=pmatrix.inverse();
					}
				}
			}
			m_matrixes[(node*range)+num]=new MMatrix(matrix);
		}
	}

	// store animations header
	tmpval=(int)m_nodes.size();
	push(tmpval); // must be same as numobjects. Or 0 if no animations (nothing follows a 0)
	tmpval=15;	// MTime::kGames
	push(tmpval); // fps
	push(range); // frames

	int objectref=0;
	for(t=0;t<m_nodes.size();t++)
	{
		MFnDagNode tmpnode(m_nodes[t]);
		push_string(tmpnode.name().asChar());
		parent=getParentIndex(t);
		push(parent);
// iInstance
		int i=-1;
		if(m_nodes[t].hasFn(MFn::kMesh))
		{
			MDagPath path;
			m_nodes[t].getPath(path);
			MFnMesh mdagNode(m_nodes[t],&status);
			if(!status) {return(MS::kFailure);}
			MString mname=mdagNode.name(&status);
			if(!status) {return(MS::kFailure);}
			for(i=0;i<(int)m_iInstances.size();i++)
			{
				if(m_iInstances[i].path.fullPathName()==path.fullPathName()) 
				{
					break;
				}
			}
		}
		if(i==(int)m_iInstances.size())
		{
			return(MS::kFailure);
		}
		push(i);
		if(!writeDecomposed(m_matrixes+(t*range),range))
		{
			return(MS::kFailure);
		}
	}
	for(t=0;t<range*m_nodes.size();t++)
	{
		delete m_matrixes[t];
	}
	delete m_matrixes;
	return(MS::kSuccess);
}

/*
	We store the animations as sampled matrixes converted into rotation quaternion, scale vector and position vector.
	The converted values are divided into ten channels, and a channel is only stored if it is used.
*/
bool Maya2Gunnar::writeDecomposed(MMatrix **matrixes,int num)
{
	float *decomposed=new float[10*num];
	MMatrix *work;
	MMatrix tmp;
	MVector ax,ay,az,scale;
	float tv;
	MQuaternion qt;
	int t,s;
	for(t=0;t<num;t++)
	{
		work=matrixes[t];
		ax=MVector(work->matrix[0][0],work->matrix[1][0],work->matrix[2][0]);
		ay=MVector(work->matrix[0][1],work->matrix[1][1],work->matrix[2][1]);
		az=MVector(work->matrix[0][2],work->matrix[1][2],work->matrix[2][2]);
		scale=MVector(ax.length(),ay.length(),az.length());
		if(scale.length()!=0)
		{
			tv=(float)((ay^az)*ax);
			if(tv<0) 
			{
				scale.x*=-1;
			}

			tv=(float)((az^ax)*ay);
			if(tv<0) 
			{
				scale.y*=-1;
			}

			tv=(float)((ax^ay)*az);
			if(tv<0) 
			{
				scale.z*=-1;
			}

			ax/=scale.x;
			ay/=scale.y;
			az/=scale.z;

			tmp=MMatrix::identity;
			tmp.matrix[0][0]=ax.x;tmp.matrix[1][0]=ax.y;tmp.matrix[2][0]=ax.z;
			tmp.matrix[0][1]=ay.x;tmp.matrix[1][1]=ay.y;tmp.matrix[2][1]=ay.z;
			tmp.matrix[0][2]=az.x;tmp.matrix[1][2]=az.y;tmp.matrix[2][2]=az.z;
			qt=tmp;
		}
		else
		{
			qt=MQuaternion::identity;
		}
		float *tc=decomposed+(t*10);
		tc[0]=(float)qt.x;tc[1]=(float)qt.y;tc[2]=(float)qt.z;tc[3]=(float)qt.w;
		tc[4]=(float)scale.x;tc[5]=(float)scale.y;tc[6]=(float)scale.z;
		tc[7]=(float)work->matrix[3][0];tc[8]=(float)work->matrix[3][1];tc[9]=(float)work->matrix[3][2];
	}
	// we have decomposed the animation into ten channels of data containing three components angle,scale and position

	// analyse channel types
	unsigned char types[10];
	for(s=0;s<10;s++)
	{
		types[s]=0; // default unanimated
		float v1=decomposed[s];
		for(t=10;t<num*10;t+=10)
		{
			if(v1!=decomposed[t+s])
			{
				types[s]=1; // raw animated
				break;
			}
		}
	}
	for(s=0;s<10;s++)
	{
		// store raw
		push(types[s]);
		switch(types[s])
		{
			case 0:
			{
				push(decomposed[s]);
				break;
			}
			case 1:
			{
				float *tc=decomposed+s;
				for(t=0;t<num*10;t+=10)
				{
					push(*(tc+t));
				}
				break;
			}
		}
	}
	delete decomposed;
	return(true);
}

BSPTree::BSPTree(MFloatPointArray &vertices,MFloatVectorArray &normals,MFloatArray &upoints, MFloatArray &vpoints,MIntArray &indices,int foff,int num_indices, bool textured)
{
	m_textured=textured;
	int i;
	for(i=0;i<(int)vertices.length();i++)
	{
		vertex v;
		if(m_textured)
		{
			v.tx=upoints[i];
			v.ty=vpoints[i];
		}
		else
		{
			v.tx=v.ty=0;
		}
		v.n=normals[i];
		v.v.x=vertices[i].x;
		v.v.y=vertices[i].y;
		v.v.z=vertices[i].z;
		m_vertices.push_back(v);
	}
	for(i=0;i<num_indices;i+=3)
	{
		triangle t;
		t.front=t.back=0xffff;
		t.i1=(unsigned short)indices[i+foff];
		t.i2=(unsigned short)indices[i+foff+1];
		t.i3=(unsigned short)indices[i+foff+2];
		t.dir=((m_vertices[t.i2].v-m_vertices[t.i1].v)^(m_vertices[t.i3].v-m_vertices[t.i1].v));
		t.dir.normalize();
		t.p=m_vertices[t.i1].v*t.dir;
		m_triangles.push_back(t);
	}
}
BSPTree::~BSPTree(void)
{
}

void BSPTree::generate(void)
{
	unsigned short start=0;
	unsigned short end=(unsigned short)m_triangles.size();
	unsigned short nstart=recursion(start,end);
	// reorder first triangle so it is in the first position.
	if(nstart!=0)
	{
		triangle a=m_triangles[0];
		m_triangles[0]=m_triangles[nstart];
		m_triangles[nstart]=a;
		for(int t=0;t<(int)m_triangles.size();t++)
		{
			if(m_triangles[t].back==0) {m_triangles[t].back=nstart;}
			else if(m_triangles[t].back==nstart) {m_triangles[t].back=0;}
			if(m_triangles[t].front==0) {m_triangles[t].front=nstart;}
			else if(m_triangles[t].front==nstart) {m_triangles[t].front=0;}
		}
	}
}
void BSPTree::pushTriangles(Maya2Gunnar *plugin)
{
	for(int t=0;t<(int)m_triangles.size();t++)
	{
		plugin->push(m_triangles[t].i1);
		plugin->push(m_triangles[t].i2);
		plugin->push(m_triangles[t].i3);
		plugin->push(m_triangles[t].dir.x);
		plugin->push(m_triangles[t].dir.y);
		plugin->push(m_triangles[t].dir.z);
		plugin->push(m_triangles[t].p);
		plugin->push(m_triangles[t].front);
		plugin->push(m_triangles[t].back);
	}
}

void BSPTree::extractVertices(MFloatPointArray &vertices,MFloatVectorArray &normals,MFloatArray &upoints, MFloatArray &vpoints,int &numfaces)
{
	vertices.clear();
	normals.clear();
	upoints.clear();
	vpoints.clear();

	int numvertices=(int)m_vertices.size();
	for(int i=0;i<numvertices;i++)
	{
		if(m_textured)
		{
			upoints.append(m_vertices[i].tx);
			vpoints.append(m_vertices[i].ty);
		}
		MFloatPoint tmppoint(m_vertices[i].v.x,m_vertices[i].v.y,m_vertices[i].v.z);
		vertices.append(tmppoint);
		normals.append(m_vertices[i].n);
	}
	numfaces=(int)m_triangles.size();
}

unsigned short BSPTree::recursion(unsigned short start, unsigned short &end)
{
	unsigned short idx=start;
	MFloatVector dir=m_triangles[start].dir;
	float p=m_triangles[start].p;
	p=tobsp_epsilon(p);
	float fd[3];
	unsigned short id[3];
	unsigned short nvert1,nvert2;
	for(unsigned short i=start+1;i<end;i++)	// only test to end
	{
		// all vertices on a triangle must be on one side of the plane, or we must cut it.
		id[0]=m_triangles[i].i1;
		id[1]=m_triangles[i].i2;
		id[2]=m_triangles[i].i3;
		fd[0]=m_vertices[id[0]].v*dir;
		fd[1]=m_vertices[id[1]].v*dir;
		fd[2]=m_vertices[id[2]].v*dir;
		float p1a=tobsp_epsilon(fd[0]-p);
		float p2a=tobsp_epsilon(fd[1]-p);
		float p3a=tobsp_epsilon(fd[2]-p);

		if(p1a<=0&&p2a<=0&&p3a<=0)
		{
			// back
			if(p1a==0&&p2a==0&&p3a==0&&idx!=start&&i!=(idx+1))
			{
				// same plane... Put it in back, and make sure we start with this triangle on the next iteration.
				triangle a=m_triangles[idx];
				triangle b=m_triangles[idx+1];
				triangle c=m_triangles[i];
				triangle d=m_triangles[start];
				m_triangles[idx+1]=a;
				m_triangles[i]=b;
				m_triangles[idx]=d;
				m_triangles[start]=c;
			}
			else if(i!=(idx+1))
			{
				triangle a=m_triangles[idx];
				triangle b=m_triangles[idx+1];
				triangle c=m_triangles[i];
				m_triangles[idx+1]=a;
				m_triangles[i]=b;
				m_triangles[idx]=c;
			}
			else
			{
				triangle a=m_triangles[idx];
				triangle b=m_triangles[i];
				m_triangles[i]=a;
				m_triangles[idx]=b;
			}
			idx++;
		}
		else if(p1a>=0&&p2a>=0&&p3a>=0)
		{
			// front, keep going.
			continue;
		}
		else
		{
			// must cut.
			// Care for the following scenarios: two vertices on one side and one on the other.
			// One vertex is on the plane and the other two is on each side.

			if(p1a==0||p2a==0||p3a==0)
			{
				// one vertex on the plane, and the two other on each side.
				while(tobsp_epsilon(fd[0]-p)!=0)
				{
					float tmp=fd[0];
					fd[0]=fd[1];
					fd[1]=fd[2];
					fd[2]=tmp;
					unsigned short tmp1=id[0];
					id[0]=id[1];
					id[1]=id[2];
					id[2]=tmp1;
				}
				// create new vertex at cut point
				vertex va=cut(id[1],id[2],fd[1],fd[2],p);
				if((nvert1=findVertex(va))==0xffff)
				{
					nvert1=(unsigned short)m_vertices.size();
					m_vertices.push_back(va);
				}
				// create triangles. The current (i) is the front, and we push in a new one at idx, and update idx+1 and end+1
				triangle a,b;
				a.dir=b.dir=m_triangles[i].dir;
				a.p=b.p=m_triangles[i].p;
				a.back=a.front=b.back=b.front=0xffff;
				a.i1=b.i1=id[0];
				a.i2=b.i2=id[1];
				a.i3=b.i3=id[2];
				if(fd[1]<p)
				{
					a.i3=nvert1;
					b.i2=nvert1;
				}
				else
				{
					a.i2=nvert1;
					b.i3=nvert1;
				}
				m_triangles[i]=b;
				m_triangles.insert(m_triangles.begin()+idx,a);
				idx++;
				end++;
				i++;
			}
			else
			{
				// two vertices on one side and one on the other. 
				// need to push in two new triangles, but where?
				while((tobsp_epsilon(fd[1]-p)<=0&&tobsp_epsilon(fd[2]-p)>=0)||(tobsp_epsilon(fd[1]-p)>=0&&tobsp_epsilon(fd[2]-p)<=0))
				{
					float tmp=fd[0];
					fd[0]=fd[1];
					fd[1]=fd[2];
					fd[2]=tmp;
					unsigned short tmp1=id[0];
					id[0]=id[1];
					id[1]=id[2];
					id[2]=tmp1;
				}
				// we know now that the first point is alone on one side, but not which side.
				vertex va=cut(id[0],id[1],fd[0],fd[1],p);
				vertex vb=cut(id[0],id[2],fd[0],fd[2],p);
				if((nvert1=findVertex(va))==0xffff)
				{
					nvert1=(unsigned short)m_vertices.size();
					m_vertices.push_back(va);
				}
				if((nvert2=findVertex(vb))==0xffff)
				{
					nvert2=(unsigned short)m_vertices.size();
					m_vertices.push_back(vb);
				}
				// create new triangles
				triangle a,b,c;
				a.dir=b.dir=c.dir=m_triangles[i].dir;
				a.p=b.p=c.p=m_triangles[i].p;
				a.back=a.front=b.back=b.front=c.back=c.front=0xffff;
				a.i1=id[0];
				b.i2=id[1];
				b.i3=c.i3=id[2];
				c.i2=b.i1=a.i2=nvert1;
				c.i1=a.i3=nvert2;

				if(fd[0]<p)
				{
					// one triangle on the back, two on the front
					m_triangles[i]=b;
					m_triangles.insert(m_triangles.begin()+idx,a);
					idx++;
					m_triangles.insert(m_triangles.begin()+idx+1,c);
				}
				else
				{
					// two triangles on the back, one on the front
					m_triangles[i]=a;
					m_triangles.insert(m_triangles.begin()+idx,b);
					m_triangles.insert(m_triangles.begin()+idx,c);
					idx+=2;
				}
				end+=2;
				i+=2;
			}
		}
	}
	unsigned short front,back,rem;
	front=back=rem=0xffff;
	if(idx>start)
	{
		rem=idx;
		back=recursion(start,idx);
		m_triangles[idx].back=back;
		end+=idx-rem;
	}
	if((idx+1)<end)
	{
		front=recursion(idx+1,end);
		m_triangles[idx].front=front;
	}
	return(idx);
}

unsigned short BSPTree::findVertex(const BSPTree::vertex &v)
{
	for(int i=0;i<(int)m_vertices.size();i++)
	{
		if(m_vertices[i]==v)
		{
			return((unsigned short)i);
		}
	}
	return(0xffff);
}

BSPTree::vertex BSPTree::cut(int a,int b,float fa,float fb,float p)
{
	vertex nv;
	float div=((p-fa)/(fb-fa));
	nv.n=((m_vertices[b].n-m_vertices[a].n)*div)+m_vertices[a].n;
	nv.v=((m_vertices[b].v-m_vertices[a].v)*div)+m_vertices[a].v;
	nv.tx=((m_vertices[b].tx-m_vertices[a].tx)*div)+m_vertices[a].tx;
	nv.ty=((m_vertices[b].ty-m_vertices[a].ty)*div)+m_vertices[a].ty;
	return(nv);
}

bool BSPTree::vertex::operator== (const vertex &vt) const
{
	MFloatVector a=vt.v-v;
	MFloatVector b=vt.n-n;
	float c=vt.tx-tx;
	float d=vt.ty-ty;
	if(abs(a.x)<=bsp_epsilon) {a.x=0;}
	if(abs(a.y)<=bsp_epsilon) {a.y=0;}
	if(abs(a.z)<=bsp_epsilon) {a.z=0;}
	if(abs(b.x)<=bsp_epsilon) {b.x=0;}
	if(abs(b.y)<=bsp_epsilon) {b.y=0;}
	if(abs(b.z)<=bsp_epsilon) {b.z=0;}
	if(abs(c)<=bsp_epsilon) {c=0;}
	if(abs(d)<=bsp_epsilon) {d=0;}
	return(a.x==0&&a.y==0&&a.z==0&&b.x==0&&b.y==0&&b.z==0&&c==0&&d==0);
}
